Étiquetage gracieux d'une figure - Olympiades 2022 Exercice 1

On considère un ensemble fini de points. On relie certains de ces points par des segments. L’ensemble ainsi constitué est appelé figure.

On effectue l’étiquetage d’une figure comportant  \(n\) segments en associant à chaque point un entier compris entre  \(0\) et \(n\) , ces entiers étant distincts deux à deux.

On attribue à chaque segment la valeur absolue de la différence des entiers associés à ses extrémités. Cet entier est appelé pondération du segment.

On dit que l’étiquetage de la figure est gracieux si les  \(n\) pondérations obtenues sur les segments sont exactement tous les entiers de  \(1\) à \(n\) .

On donne ci-dessous un exemple d’étiquetage gracieux d’une figure comportant  \(6\) points et  \(7\) segments :

Figure étiquetée.

Figure étiquetée avec indication des pondérations/

A. Des exemples

1. Pour chacune des figures ci-dessous, préciser si l’étiquetage proposé est un étiquetage gracieux.

2. Compléter l’étiquetage de la figure ci-dessous pour obtenir un étiquetage gracieux.

B. Cas des lignes

Pour tout entier naturel non nul \(n\) , on considère la figure  \(L_n\) constituée de  \(n+1\) points alignés et des  \(n\) segments joignant des points voisins.

On propose ci-dessous l’étiquetage gracieux des points de la figure \(L_4\) .

1. Montrer qu’on peut trouver un étiquetage gracieux pour chacune des figures \(L_5\) ,  \(L_6\) et \(L_7\) .

2. On admet qu’on peut trouver un étiquetage gracieux pour la figure \(L_{2022}\) tel que le point le plus à gauche soit étiqueté avec \(0\) . Décrire cet étiquetage.

C. Cas des polygones

1. Montrer que tout triangle et tout quadrilatère peut être muni d’un étiquetage gracieux.

2. On a représenté ci-dessous un polygone à  \(11\) côtés muni d’un étiquetage gracieux.

En déduire un étiquetage gracieux pour un polygone à \(12\)  côtés.

3. Déterminer la parité de la pondération d’un segment lorsque les étiquettes de ses extrémités sont :
      a. de parités différentes ;
      b. de même parité.

4. En déduire qu’on ne peut pas trouver un étiquetage gracieux pour les pentagones.

D. Une très grande figure

On note \(k_{2022}\)  la figure constituée de  \(2\,022\) points telle que tout couple de points est relié par un unique segment.

1. Montrer que  \(k_{2022}\) est constituée de  \(2\,043\,231\)  segments.

2. On suppose qu’il existe d’un étiquetage gracieux de \(k_{2022}\) .
       a. Quel est le nombre de segments dont la pondération est un nombre impair ?
       b. On note  \(p\) le nombre de points étiquetés avec un nombre pair. Exprimer en fonction de  \(p\) le nombre de segments dont la pondération est un nombre impair.

3. Montrer finalement que  \(k_{2022}\) ne peut pas être muni d’un étiquetage gracieux.